package com.yanceysong.codetop.s91_s100;

import java.util.Arrays;

public class S100_Mid_补充题6_手撕堆排序 {
    /**
     * .S100_Mid_补充题6_手撕堆排序
     * .<p>
     * .堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。
     * .它利用堆这种数据结构所设计的一种排序算法。
     * .<p>
     * .核心标签：排序、堆、数组、二叉树
     * .<p>
     * .算法原理：
     * .1. 构建最大堆：将无序数组调整为最大堆（父节点 >= 子节点）
     * .2. 排序阶段：
     * .- 将堆顶元素（最大值）与末尾元素交换
     * .- 将堆的大小减1
     * .- 对新的堆顶元素进行下沉调整，维护最大堆性质
     * .- 重复上述步骤，直到堆的大小为1
     * .<p>
     * .堆的性质：
     * .- 完全二叉树：除了最后一层，其他层都是满的，最后一层从左到右填充
     * .- 最大堆：每个节点的值都大于或等于其子节点的值
     * .- 数组表示：对于索引 i 的节点
     * .- 父节点索引：(i - 1) / 2
     * .- 左子节点索引：2 * .i + 1
     * .- 右子节点索引：2 * .i + 2
     * .<p>
     * .关键洞察：
     * .1. 堆排序是原地排序算法，不需要额外的存储空间
     * .2. 堆排序是不稳定的排序算法（相同元素的相对位置可能改变）
     * .3. 构建堆的时间复杂度是 O(n)，而不是 O(n log n)
     * .4. 最后一个非叶子节点的索引是 n/2 - 1
     * .5. 堆排序的性能不受输入数据的影响，始终是 O(n log n)
     * .<p>
     * .图解示例：arr = [4, 10, 3, 5, 1]
     * .<p>
     * .第一阶段：构建最大堆
     * .<p>
     * .原始数组：[4, 10, 3, 5, 1]
     * .<p>
     * .数组表示的完全二叉树：
     * .      4
     * .     / \
     * .    10  3
     * .   / \
     * .  5   1
     * .<p>
     * .步骤1：从最后一个非叶子节点开始（索引 1，值为 10）
     * .节点 10 的子节点：5 和 1
     * .10 > 5 且 10 > 1，无需调整
     * .<p>
     * .步骤2：调整节点 0（值为 4）
     * .节点 4 的子节点：10 和 3
     * .10 > 4，交换 4 和 10
     * .<p>
     * .      10
     * .     /  \
     * .    4    3
     * .   / \
     * .  5   1
     * .<p>
     * .继续调整被交换的节点 4（现在在索引 1）
     * .节点 4 的子节点：5 和 1
     * .5 > 4，交换 4 和 5
     * .<p>
     * .      10
     * .     /  \
     * .    5    3
     * .   / \
     * .  4   1
     * .<p>
     * .最大堆构建完成：[10, 5, 3, 4, 1]
     * .<p>
     * .第二阶段：排序
     * .<p>
     * .轮次1：交换堆顶和末尾元素
     * .[10, 5, 3, 4, 1] → [1, 5, 3, 4, | 10]
     * .调整堆（大小为4）：
     * .      1
     * .     / \
     * .    5   3
     * .   /
     * .  4
     * .<p>
     * .1 < 5，交换 1 和 5
     * .      5
     * .     / \
     * .    1   3
     * .   /
     * .  4
     * .<p>
     * .1 < 4，交换 1 和 4
     * .      5
     * .     / \
     * .    4   3
     * .   /
     * .  1
     * .<p>
     * .结果：[5, 4, 3, 1, | 10]
     * .<p>
     * .轮次2：交换堆顶和末尾元素
     * .[5, 4, 3, 1, | 10] → [1, 4, 3, | 5, 10]
     * .调整堆（大小为3）：
     * .      1
     * .     / \
     * .    4   3
     * .<p>
     * .1 < 4，交换 1 和 4
     * .      4
     * .     / \
     * .    1   3
     * .<p>
     * .结果：[4, 1, 3, | 5, 10]
     * .<p>
     * .轮次3：交换堆顶和末尾元素
     * .[4, 1, 3, | 5, 10] → [3, 1, | 4, 5, 10]
     * .调整堆（大小为2）：
     * .      3
     * .     /
     * .    1
     * .<p>
     * .3 > 1，无需调整
     * .结果：[3, 1, | 4, 5, 10]
     * .<p>
     * .轮次4：交换堆顶和末尾元素
     * .[3, 1, | 4, 5, 10] → [1, | 3, 4, 5, 10]
     * .<p>
     * .最终排序结果：[1, 3, 4, 5, 10]
     * .<p>
     * .堆调整（heapify）过程详解：
     * .<p>
     * .对于节点 i：
     * .1. 找出 i、left(i)、right(i) 中的最大值
     * .2. 如果最大值不是 i，则交换 i 和最大值
     * .3. 递归调整被交换的子树
     * .<p>
     * .示例：调整节点 0（值为 4）
     * .<p>
     * .      4
     * .     / \
     * .    10  3
     * .   / \
     * .  5   1
     * .<p>
     * .left = 10, right = 3
     * .largest = 10（索引 1）
     * .交换 4 和 10：
     * .<p>
     * .      10
     * .     /  \
     * .    4    3
     * .   / \
     * .  5   1
     * .<p>
     * .递归调整节点 1（值为 4）：
     * .left = 5, right = 1
     * .largest = 5（索引 3）
     * .交换 4 和 5：
     * .<p>
     * .      10
     * .     /  \
     * .    5    3
     * .   / \
     * .  4   1
     * .<p>
     * .节点 3 是叶子节点，调整结束
     * .<p>
     * .时间复杂度：O(n log n)
     * .- 构建堆：O(n)
     * .- 排序阶段：n 次循环，每次调整 O(log n)，总共 O(n log n)
     * .<p>
     * .空间复杂度：O(1)
     * .- 原地排序，只使用常数个额外变量
     * .- 递归调用栈深度为 O(log n)，但可以改为迭代实现
     * .<p>
     * .堆排序的优缺点：
     * .<p>
     * .优点：
     * .1. 时间复杂度稳定，始终是 O(n log n)
     * .2. 原地排序，空间复杂度 O(1)
     * .3. 不受输入数据影响，最好、最坏、平均情况都是 O(n log n)
     * .<p>
     * .缺点：
     * .1. 不稳定排序（相同元素的相对位置可能改变）
     * .2. 实际性能通常不如快速排序
     * .3. 缓存不友好（访问模式不连续）
     */
    public static void heapSort(int[] arr) {
        int arrayLength = arr.length;

        // 第一阶段：构建最大堆
        // 从最后一个非叶子节点开始，向上调整每个节点
        // 最后一个非叶子节点的索引是 arrayLength / 2 - 1
        for (int i = arrayLength / 2 - 1; i >= 0; i--) {
            heapify(arr, arrayLength, i);
        }

        // 第二阶段：排序
        // 逐个将堆顶元素（最大值）移到数组末尾
        for (int i = arrayLength - 1; i > 0; i--) {
            // 将当前堆顶（最大值）与末尾元素交换
            swap(arr, 0, i);

            // 调整剩余元素为最大堆（堆大小减1）
            // 只需要调整堆顶元素，因为其他元素仍然满足堆的性质
            heapify(arr, i, 0);
        }
    }

    /**
     * .堆调整（下沉操作）
     * .将指定节点调整到正确位置，使其满足最大堆的性质
     *
     * .@param arr       待调整数组
     * .@param heapSize  当前堆的有效大小
     * .@param nodeIndex 待调整节点的索引
     */
    private static void heapify(int[] arr, int heapSize, int nodeIndex) {
        // 初始化最大值索引为当前节点
        int largestIndex = nodeIndex;

        // 计算左子节点和右子节点的索引
        int leftChildIndex = 2 * nodeIndex + 1;  // 左子节点索引
        int rightChildIndex = 2 * nodeIndex + 2; // 右子节点索引

        // 比较左子节点与当前最大值
        // 如果左子节点存在且大于当前最大值，更新最大值索引
        if (leftChildIndex < heapSize && arr[leftChildIndex] > arr[largestIndex]) {
            largestIndex = leftChildIndex;
        }

        // 比较右子节点与当前最大值
        // 如果右子节点存在且大于当前最大值，更新最大值索引
        if (rightChildIndex < heapSize && arr[rightChildIndex] > arr[largestIndex]) {
            largestIndex = rightChildIndex;
        }

        // 如果最大值不是当前节点，则需要交换并继续调整
        if (largestIndex != nodeIndex) {
            // 交换当前节点和最大值节点
            swap(arr, nodeIndex, largestIndex);

            // 递归调整被交换的子树
            // 因为交换可能破坏了子树的堆性质
            heapify(arr, heapSize, largestIndex);
        }
    }

    /**
     * .交换数组中两个位置的元素
     *
     * .@param arr 数组
     * .@param i   第一个位置
     * .@param j   第二个位置
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        System.out.println("=== 堆排序测试开始 ===");

        // 测试1: 基本测试 [12, 11, 13, 5, 6, 7]
        System.out.println("\n--- 测试1: 基本测试 ---");
        testCase1();

        // 测试2: 已排序数组（升序）
        System.out.println("\n--- 测试2: 已排序数组（升序）---");
        testSortedArray();

        // 测试3: 逆序数组
        System.out.println("\n--- 测试3: 逆序数组 ---");
        testReverseSortedArray();

        // 测试4: 包含重复元素
        System.out.println("\n--- 测试4: 包含重复元素 ---");
        testDuplicateElements();

        // 测试5: 单元素数组
        System.out.println("\n--- 测试5: 单元素数组 ---");
        testSingleElement();

        // 测试6: 两个元素
        System.out.println("\n--- 测试6: 两个元素 ---");
        testTwoElements();

        // 测试7: 所有元素相同
        System.out.println("\n--- 测试7: 所有元素相同 ---");
        testAllSameElements();

        // 测试8: 包含负数
        System.out.println("\n--- 测试8: 包含负数 ---");
        testNegativeNumbers();

        // 测试9: 包含零
        System.out.println("\n--- 测试9: 包含零 ---");
        testWithZero();

        // 测试10: 大数组
        System.out.println("\n--- 测试10: 大数组 ---");
        testLargeArray();

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: 基本测试 [12, 11, 13, 5, 6, 7]
     * .期望输出：[5, 6, 7, 11, 12, 13]
     */
    private static void testCase1() {
        int[] arr = {12, 11, 13, 5, 6, 7};
        int[] expected = {5, 6, 7, 11, 12, 13};

        System.out.println("原始数组: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试1失败";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: 已排序数组（升序）[1, 2, 3, 4, 5]
     * .期望输出：[1, 2, 3, 4, 5]
     */
    private static void testSortedArray() {
        int[] arr = {1, 2, 3, 4, 5};
        int[] expected = {1, 2, 3, 4, 5};

        System.out.println("原始数组: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试2失败";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 逆序数组 [5, 4, 3, 2, 1]
     * .期望输出：[1, 2, 3, 4, 5]
     */
    private static void testReverseSortedArray() {
        int[] arr = {5, 4, 3, 2, 1};
        int[] expected = {1, 2, 3, 4, 5};

        System.out.println("原始数组: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试3失败";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 包含重复元素 [4, 2, 4, 1, 3, 2]
     * .期望输出：[1, 2, 2, 3, 4, 4]
     */
    private static void testDuplicateElements() {
        int[] arr = {4, 2, 4, 1, 3, 2};
        int[] expected = {1, 2, 2, 3, 4, 4};

        System.out.println("原始数组: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试4失败";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 单元素数组 [42]
     * .期望输出：[42]
     */
    private static void testSingleElement() {
        int[] arr = {42};
        int[] expected = {42};

        System.out.println("原始数组: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试5失败";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 两个元素 [2, 1]
     * .期望输出：[1, 2]
     */
    private static void testTwoElements() {
        int[] arr = {2, 1};
        int[] expected = {1, 2};

        System.out.println("原始数组: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试6失败";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 所有元素相同 [5, 5, 5, 5, 5]
     * .期望输出：[5, 5, 5, 5, 5]
     */
    private static void testAllSameElements() {
        int[] arr = {5, 5, 5, 5, 5};
        int[] expected = {5, 5, 5, 5, 5};

        System.out.println("原始数组: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试7失败";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 包含负数 [-5, 3, -1, 7, -9, 2]
     * .期望输出：[-9, -5, -1, 2, 3, 7]
     */
    private static void testNegativeNumbers() {
        int[] arr = {-5, 3, -1, 7, -9, 2};
        int[] expected = {-9, -5, -1, 2, 3, 7};

        System.out.println("原始数组: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试8失败";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 包含零 [0, -1, 5, 0, 3, -2]
     * .期望输出：[-2, -1, 0, 0, 3, 5]
     */
    private static void testWithZero() {
        int[] arr = {0, -1, 5, 0, 3, -2};
        int[] expected = {-2, -1, 0, 0, 3, 5};

        System.out.println("原始数组: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后:   " + Arrays.toString(arr));
        System.out.println("期望:     " + Arrays.toString(expected));

        assert Arrays.equals(arr, expected) : "测试9失败";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 大数组（100个元素）
     * .期望输出：升序排列
     */
    private static void testLargeArray() {
        int[] arr = new int[100];
        // 填充随机数据（使用固定种子以便验证）
        for (int i = 0; i < 100; i++) {
            arr[i] = 100 - i; // 逆序
        }

        System.out.println("原始数组: [100, 99, 98, ..., 3, 2, 1]");
        heapSort(arr);
        System.out.print("排序后:   [");
        for (int i = 0; i < 10; i++) {
            System.out.print(arr[i] + (i < 9 ? ", " : ""));
        }
        System.out.println(", ..., " + arr[99] + "]");

        // 验证数组是否已排序
        for (int i = 0; i < arr.length - 1; i++) {
            assert arr[i] <= arr[i + 1] : "数组未正确排序";
        }

        System.out.println("✓ 测试10通过");
    }
}

